#include <iostream>

typedef char T;

using namespace std;

template <typename T>
struct QueueNode {
    T data;
    int priority;
    QueueNode* next;

	QueueNode() :next(NULL) {}
    QueueNode(T data, int priority, QueueNode* next):
        data(data), priority(priority), next(next) {}
};


template <typename T>
class PriorityQueue {
    QueueNode<T>* front;

    public:
    PriorityQueue<T>():front(new QueueNode<T>()) {}
    void insert(T data, int priority);
    bool isEmpty();
    T peek();
    T pullPeek();
	int getPriority(T data);
	void peeks();
	void clear();
    int length();
	void insertMany(T* somedata, int* priorities, int count);
	void merge(PriorityQueue* pqs, int count);
	bool changePriority(T data, int priority);

};


class NullElementException {};
class ElementNotFoundException {};


template <typename T>
void PriorityQueue<T>::insert(T data, int priority) {
    QueueNode<T>* curQueueNode = front;

    while(curQueueNode->next && priority <= curQueueNode->next->priority) {
        curQueueNode = curQueueNode->next;
    }

    curQueueNode->next = new QueueNode<T>(data, priority, curQueueNode->next);
}


template <typename T>
bool PriorityQueue<T>::isEmpty() {
    return front->next?false:true;
}


template <typename T>
T PriorityQueue<T>::peek() {
    if(isEmpty()) throw new NullElementException();
    else return front->next->data;
}


template <typename T>
T PriorityQueue<T>::pullPeek() {
    T data = peek();

    QueueNode<T>* first = front->next;
    front->next = first->next;
    delete first;

    return data;
}


template <typename T>
int PriorityQueue<T>::getPriority(T data) {
	QueueNode<T>* curQueueNode = front;

	while (curQueueNode->next) {
		curQueueNode = curQueueNode->next;
		if (curQueueNode->data == data) return curQueueNode->priority;
	}

	throw new ElementNotFoundException();
}


template <typename T>
void PriorityQueue<T>::peeks() {
	if (isEmpty()) throw new NullElementException();

	int priority = front->next->priority;

	QueueNode<T>* curQueueNode = front->next;

	while (curQueueNode && curQueueNode->priority == priority) {
		cout << curQueueNode->data << " ";
		curQueueNode = curQueueNode->next;
	}
}


template <typename T>
void PriorityQueue<T>::clear() {
	if (isEmpty()) return;

	QueueNode<T>* curQueueNode = front;
	QueueNode<T>* tempQueueNode;

	while (curQueueNode->next) {
		tempQueueNode = curQueueNode->next;
		curQueueNode->next = tempQueueNode->next;
		delete tempQueueNode;
	}
}


template <typename T>
int PriorityQueue<T>::length() {
    int length = 0;
    QueueNode<T>* curQueueNode = front->next;

    while(curQueueNode) {
        length++;
        curQueueNode = curQueueNode->next;
    }

    return length;
}


template <typename T>
void PriorityQueue<T>::insertMany(T* somedata, int* priorities, int count) {
	for (int i = 0; i < count; i++) {
		insert(somedata[i], priorities[i]);
	}
}


template <typename T>
void PriorityQueue<T>::merge(PriorityQueue* pqs, int count) {
	T data;
	int priority;
	for (int i = 0; i < count; i++) {
		QueueNode<T>* curQueueNode = pqs[i].front;
		while (curQueueNode->next) {
			curQueueNode = curQueueNode->next;
			data = curQueueNode->data;
			priority = pqs[i].getPriority(data);
			insert(data, priority);
		}
	}
}


template <typename T>
bool PriorityQueue<T>::changePriority(T data, int priority) {
	QueueNode<T>* curQueueNode = front;

	while (curQueueNode->next) {
		curQueueNode = curQueueNode->next;
		if (curQueueNode->data == data) {
			curQueueNode->priority = priority;
			return true;
		}
	}

	return false;
}
